package ljl.alg.hot100;

public class _169_majority_element {
    
    /*
    * 没什么意思其实
    * 有一个元素能干过所有其它元素所以直接换血就行了
    *
    * 哎我去？改了好几版才改对
    * 之前是以 nums[i] 为主体，发现不行，得以 c 为主体
    *
    * */
    public int majorityElement1(int[] nums) {
        int c = 1, prev = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (c == 0) {
                prev = nums[i];
                c = 1;
            } else {
                if (nums[i] == prev) {
                    c++;
                } else {
                    c--;
                }
            }
        }
        return prev;
    }
    
    // 还可以数个数
    
    // 还可以 Arrays.sort 然后取 n/2
    
    // 还可以分治，不太聪明，不太喜欢这个解法，还是写一下吧
    // 感觉这个解法非常的傻屄
    /**
     * 有点傻屄
     * */
    int count(int[] nums, int from ,int to, int num) {
        int c = 0;
        for (int i = from; i <= to; i++) {
            if (nums[i] == num) c++;
        }
        return c;
    }
    
    int dc(int[] nums, int from, int to) {
        if (from == to) return nums[from];
        int mid = (from + to) / 2;
        int left = dc(nums, from ,mid);
        int right = dc(nums, mid + 1, to);
        if (left == right) return left;
        int c1 = count(nums, from, mid, left);
        int c2 = count(nums, mid + 1, to, right);
        return c1 > c2 ? left : right;
    }
    
    public int majorityElement(int[] nums) {
        return dc(nums, 0, nums.length - 1);
    }
}
